\chapter{Automated Control Signal Identification}
A design may operate in various modes based on the values taken by its
control signals. Examples of control signals include signals for reset,
mode selection, communication, as well as those introduced by the
Electronic Design Automation (EDA) tools such as the ones for power gating
and clock gating \cite{LeeSC12}. Control signals can greatly impact the
quality of trace signal selection process and the subsequent restoration of
the not-traced signals. Therefore, in this chapter we study automatic
identification of control signals in a design which will later be
incorporated to improve the quality of the trace signal selection process
and signal restoration.

In this chapter, we propose an automated control signal identification
procedure based on using the X-Simulation and a set of defined metrics in
order to automatically identify the control signals in a short amount of
time. Our focus will be on those control signals which are a subset of
primary inputs with much larger impact on the rest of the design and
identifying non-primary input control signals are not within the scope of
this work.

In this chapter in Section \ref{sec:csim}, we first will give a definition
of the control signals and illustrate their impact on trace signal
selection using an example. In Section \ref{sec:csbg}, we will discuss some
prior works on control signal identification and in Section
\ref{sec:csalg}, we present an automated control signal identification
procedure which can identify the control signals in a short amount of
time. Finally, simulation results will be shown in Section
\ref{sec:results_cs}.
\newpage

\section{Control Signals and Their Impact on State Restoration}\label{sec:csim}
\begin{figure}[t]
  \centering
  \includegraphics[width=3.0in]{figs/example_cs.eps}
  \caption{Example circuit for explaining the control signals}
  \label{fig:example_cs}
\end{figure}

Control signals typically have a much lower switching activity compared to
the other primary inputs in a design. However, selection of the trace
signals based on unrealistic changing of the control signals (e.g., random
assignment in simulation) may yield to a significantly poor restoration for
any of the individual operation modes. The simplest example is a `reset'
signal which should be set to inactive when evaluating the restoration
within the trace signal selection process.  Otherwise, by assuming `reset'
can take any value using random assignment, the selected traces may have a
much higher restoration quality than reality. In practice, the values of
the control signals can also be used to restore the remaining state
elements and impact the solution quality in terms of SRR for the same
circuit with different operation modes.

Figure \ref{fig:example_cs} shows a simple example of a circuit with a
control signal. Here, $c$ is a control signal which is connected to the
inputs of an AND and an OR gate. When $c$ takes a value of `0', the signal
value coming out of $f_1$ to the AND gate will be blocked since $c$ is
dominating. When $c$ takes a value of `1', the signal value coming out of
$f_2$ to the OR gate will be blocked similarly. Therefore in this example,
the amount of restoration in the state elements is directly affected by the
value of the control signal, regardless of which state element may be
selected for tracing.
%As will be shown in Chapter 6, different operation modes which are decided by different of  can add complexity.

\section{Background and Related Works}\label{sec:csbg}
%rephraze the first sentence
Although the functionality of each input signal may be clear to the
engineers at the early stages of the design process, these information may
not be accessible to the validation engineers after all design blocks are
integrated and the circuit is synthesized into a gate-level netlist
\cite{JTG13}. This is because validation engineers may only be able to
coarsely categorize the inputs into three types: data inputs, address
inputs and control inputs, based on limited information of the input
signals at the gate-level.

Some control inputs can only influence a small portion of the circuit
(e.g., an enable signal to turn on/off a design block with only a few
gates) while others can impact a large portion (e.g., a signal for
communication between multiple cores). In this work, we only consider those
control signals which can significantly impact the circuit operation and
the quality of trace signal selection. Identifying these signals should be
done prior to the trace signal selection process.

Previous works have proposed control signal identification procedures for
different validation purposes. The work \cite{JTG13} proposed a method to
identify the control signals to assist static validation in order to check
the connectivity and functionality of the fan-out networks of the control
signals. The procedure starts from the known control signals at higher
levels of the design hierarchy and backtracks to identify the control
signals at the lower levels. However its application is limited and the
procedure requires the netlist to be available.

The work \cite{KoDis} also studied identification of the control signals in
order to assist the design of the post-silicon validation infrastructure
using trace buffers. The identification was also done prior to selecting
the trace signals. The work \cite{KoDis} then described a flow to identify
the control signals that can affect the trace signal selection. Basically,
the control signals were identified using Automatic Test Pattern Generation
(ATPG) \cite{GuptaH04} from the perspective of error propagation. If a
signal has a high ``care-bit'' density, then it should be considered as a
control signal. Here care-bit density helps identify if the values of a
signal are unknown for most of the ATPG-generated test patterns.
%\todo[inline,linecolor=green!70!white, backgroundcolor=blue!20!white,
%bordercolor=red]{Just want to keep this for record of the use of tofo list} 
This method is both capable of identifying the control signals and deciding
their values. However, it has only been tested for small ISCAS'89
benchmarks; for large benchmarks, the runtime of ATPG becomes prohibitively
large since the setup of ATPG in \cite{KoDis} requires considering all
possible stuck-at-fault positions of the design with a high fault coverage
requirement.

Similar to \cite{KoDis}, in this dissertation, the goal of control signal
identification is to figure out those input control signals that have a
significant impact on the quality of trace signal selection. We assume only
gate-level netlists are available for identification, which is consistent
with the situation described in \cite{JTG13, KoDis}. We then propose an
automated control signal identification procedure which makes use of the
fast X-Simulation and limited knowledge of the inputs. Our identification
procedure is much simpler than the error propagation mechanism related to
different fault types which was used in \cite{KoDis}. It is capable of
selecting the input signals that have significant impact on the trace
signal selection quality. Our procedure also has a good runtime-scalability
and is able to identify the control signals in a short amount of time.

\section{Algorithm for Automated Control Signal Identification}\label{sec:csalg}
Our identification procedure has the following key features: i) it is able
to effectively prune out the signals that have less impact on restoration,
ii) it is able to decide the feasible values of the control signals, such
as active-high or active-low for the reset signals, iii) it has a good
scalability over large circuits. The whole identification procedure
contains the following steps as described in the flow chart shown in Figure
\ref{fig:cs_ident_flow}.

Here is an overview of our identification procedure. It starts by computing
a metric which is the number of restored gates for each primary input when
it takes the value of `0' and `1' respectively. A ranking of all primary inputs
is obtained based on the values of the metric in descending order. Then the
ones with metric values larger than a threshold will be selected as
candidates to be considered as control signals. Finally, input information
is used to decide the control signals among the candidates, together with
the values they can take. Next we explain these steps in more detail.

\begin{figure}[t]
\centering
    \includegraphics[width=2.0in]{figs/cs_ident_flow.pdf}
    \caption{Control Signal Identification Flow}
    \label{fig:cs_ident_flow}
\end{figure}

{\bf In step 1 of the identification process}, the impact of each primary
input is quantified by looking at the {\it number} of gates that it can
restore. In this step, for each primary input, we use the fast X-Simulator
to perform the state restoration process to the circuit when {\it only}
that input signal takes a known value and the rest of the primary inputs
take the unknown value. (All state elements also take unknown values.) We
record the number of gates that are restored when the input signal takes
value `0' and `1' respectively. The summation of the two numbers is then
used as the metric for the ranking of that input signal. It is obvious that
the larger this metric is, the more gates will be `controlled' by that
signal.

\begin{figure}[t]
\centering
    \includegraphics[width=4.8in]{figs/ctr_ident_dsp.pdf}
    \caption{Identifying the gates restored by four (control and
    non-control) input signals in benchmark circuit {\tt dsp} from the ISPD'12
    gate sizing benchmark suite}
    \label{fig:ctr_ident_dsp}
\end{figure}

As an example, Figure \ref{fig:ctr_ident_dsp} shows the number of gates
that can be restored by four representative input signals separately in
benchmark {\tt dsp} from the ISPD'12 gate sizing benchmark suite
\cite{ISPD12} after applying step 1. To generate the plot, first each gate
is assigned to a unique position/coordinate which remains the same in all
the four subplots. Each blue dot refers to a gate that is restored by the
signal whose name is listed on top of each subplot. We can see from the
plot that input signal `T\_ICE\_RSTn' can restore the most gates, followed
by `T\_TMODE[1]', `T\_IMS' and `T\_IAL'.

Please note the number of gates restored by a single control signal may
still be a very small portion of the total number of gates. 
For example, in benchmark {\tt b18}, the number of gates directly restored
by control signal `sel' is only 6.1\% of the total number of
gates. However, since the input control signals typically lie in the early
topological stages of the circuit, their impacts can be propagated far deep
into the remaining logic. Exact measurement of the impacts of the control
signals is hard to achieve, since it will turn the identification problem
back to the complicated ATPG-based approach in \cite{KoDis}, which is
time-consuming because it requires the incorporation of the other input
signals and the consideration of different fault types.

{\bf In step 2 of our identification process}, the metric value of each
primary input is normalized to the largest metric value among all primary
inputs. This is because, to come up with a general rule that can be applied
to all benchmarks, absolute values of the number of restored gates need to
be normalized. Next, all primary inputs are ranked based on the normalized
metric values in descending order and only the ones with normalized values
greater than an \emph{Impact Factor} will be considered as potential
control signals. Primary inputs with the metric values less than the Impact
Factor usually have a negligible influence on trace signal selection
quality thus do not need to be constrained. The value of Impact Factor used
in this work is 0.1, which is selected after experimenting with a wide
range of existing benchmarks of various sizes and circuit topologies. Given
this setup, the average percentage of potential control signals among all
benchmarks is only 5.1\% of the total primary inputs, which shows that
simulation can greatly narrow down the scope of potential control signals.

{\bf In step 3 of our identification process}, we prune the
candidates identified from step 2 and find the control signals. Pruning is
necessary because not all signals with high rankings can be considered as
control signals. For example, sometimes a few bits in address inputs can
restore a large amount of gates whereas they should not be considered as
control signals (as is the case for benchmark {\tt DMA}).

One may argue that a pruning procedure can be applied before the simulation
step to separate control inputs from the other input types and only perform
X-Simulation for the control inputs. However this requires manual
intervention whereas our procedure is almost-fully automated and has a very
quick runtime. For example, we will show later in the experimental results
that the simulation time for a large circuit (with 150k gates and 230
primary inputs) is around 12 seconds, therefore it is completely feasible
to use X-Simulation to perform the coarse-grained but quite effective
pruning step first, before applying human knowledge to finalize the control
signals. Also, most of the bits in data or address inputs have low rankings
and consume a small portion of the simulation time, thus will be automatically
ruled out after steps 1 and 2.

{\bf Finally, at step 4 of our identification procedure} 
we decide the relevant and feasible values of the control
signals. Specifically, if the number of gates restored when a signal takes
value `0' is comparable to the number of gates restored when that signal
takes value `1', then the control signal can take either `0' or `1' during
operation, resulting in two different modes. If there is a strong bias in
the two cases, we would further need the information reflecting the
functional impact of the signal on the circuit in order to decide the value
it should take. For a signal that is used for reset such as a global reset,
its value should be set to the non-controlling value to ensure that it does
not lead to many restored gates during the operation. However, signals
which are not used as reset should be able to take either `0' or `1' no
matter how biased the situation is, indicating two different modes per such
signal.

Therefore, the reset signals need to be identified as a part of the step 4.
A reset signal can be identified based on two features, which usually
appear at the same time. First, a reset signal always has the highest
metric value. For example, among the benchmarks used for experiments in
this chapter, three reset signals are identified: `RESET' in benchmark {\tt
S35932} from the ISCAS'89 benchmark suite \cite{ISCAS89}, `T\_ICE\_RSTn'
and `T\_RSTn' in benchmark {\tt dsp} from the ISPD'12 gate sizing benchmark
suite \cite{ISPD12}. Here, `RESET' has the highest metric value in
benchmark {\tt S35932}; `T\_ICE\_RSTn' and `T\_RSTn' have the same metric
value, which is higher than the rest primary inputs in benchmark {\tt dsp}
(as will be shown in the experimental results). Second, after applying step
3, a ratio is computed for each candidate to help identify the reset
signals. Specifically, this ratio is computed by using the number of gates
restored when a signal takes the non-controlling value, divided by the
number of gates restored when it takes the controlling value. Note here,
when a signal takes the non-controlling value, much fewer gates will be
restored than the case when it takes the controlling value. Usually, this
ratio is the smallest for a reset signal.

\section{Experimental Results} \label{sec:results_cs}
We verify our control signal identification algorithm using a subset of
ISCAS'89 \cite{ISCAS89}, IWLS'05 \cite{IWLS05}, and ISPD'12 gate sizing
contest \cite{ISPD12} benchmarks. These are the benchmarks we identified to
have control signals. Moreover, the IWLS'05 and ISPD'12 benchmarks are much
larger in size than the benchmarks used in previously published works. Table
\ref{tab:cs} shows the results of control signal identification after
following the steps described in Section \ref{sec:csalg}.

The number of primary inputs per benchmark is on average 235 as shown in
column 2. Note that when running the identification procedure on these
benchmarks, each bit in a data or address input (or other grouped signals)
is treated as a separate primary input (such as the `haddr[4]' and
`haddr[5]' in group `haddr' from the benchmark {\tt DMA}). 

\subsection{Identifying Top Control Signal Candidates}
Table \ref{tab:cs} column 4 shows the percentage of
candidate control signals after imposing the steps (1-3) described in
Section \ref{sec:csalg}. The Impact Factor is set to 0.1 in the simulation
setup as explained before. The percentage of control signal candidates
ranges from 0.4\% to 16.2\% of the total primary inputs, with an average 
value of 5.1\%. This shows that steps (1) and (2)
in Section \ref{sec:csalg} can effectively prune non-control primary input
signals to identify an overall small number of control signal candidates. 
In addition, this step is fast as can be seen
from the runtime of simulation, as shown in column 5 of the
table. Even for the largest benchmark {\tt des\_perf} with 150K gates and
234 inputs, the runtime is around 12 seconds. Finally, column 3 shows the number of
control signals identified for each benchmark. Note this number excludes any reset signal. 

\begin{table}[t]
  \centering
  \caption{Stats of the Control Signal Identification Process}
    \begin{tabular}{c|cccc}
    \toprule
    \multicolumn{1}{c|}{Bench} & \#PIs & \#CtrolSignals & \%Candidates & Runtime(sec) \\
    \midrule
    {\tt S38584}    & 38    & 1     & 5.3\%  & 2.19 \\
    {\tt S35932}    & 35    & 2     & 8.6\%  & 2.35 \\
    {\tt b17}       & 37    & 2     & 16.2\% & 0.76 \\
    {\tt b18}       & 36    & 1     & 2.8\%  & 1.62 \\
    {\tt dsp}       & 586   & 3     & 0.9\%  & 8.49 \\
    {\tt DMA}       & 682   & 3     & 1.8\%  & 6.63 \\
    {\tt des\_perf} & 234   & 1     & 0.4\%  & 11.55 \\
\hline
    Avg.            & 235   & 1.86  & 5.1\%  & 4.80 \\
    \bottomrule
    \end{tabular}%
  \label{tab:cs}%
\end{table}%


\subsection{Identifying Control Signals from the Top Candidates}
As briefly mentioned in step 3 of our identification algorithm, some
address inputs can be identified as control signal candidates but they
should not be considered as control signals. By looking at benchmark {\tt
DMA}, we now show how our procedure is able to identify the control signals
from the top candidates. Figure \ref{fig:DMA_cs} (a) shows the identified
control signal candidates after step 2 and Figure \ref{fig:DMA_cs} (b) shows
the finalized control signals. Here signal `hadder[3]' has the highest
ranking. However it is an address bit and should not be considered as a
control signal. Similarly, other signals which are address inputs appear as
top candidates. However eventually all such signals are pruned out
leaving only 3 signals in the end as shown in Figure 5.4 (b).

\begin{figure}[t]
\centering
    \includegraphics[width=4.0in]{figs/DMA_cs.pdf}
    \caption{Deciding the Control Signals for {\tt DMA} after X-Simulation.
      (a) identifying the top control signal candidates in benchmark {\tt
      DMA}; (b) final identified control signals.}
    \label{fig:DMA_cs}
\end{figure}

\subsection{Group Identification of Control Signals}
Control signals may also be identified in group using naming
similarity. This allows to further identify some signals which may not
necessarily have a high impact factor. For example, consider the benchmark
{\tt dsp}. After applying the steps of our algorithm, signals
`T\_ICE\_RSTn' and `T\_RSTn' are identified as reset signals and signals
`T\_TMODE[1]' and `T\_IMS' are identified as control signals because of
having a very high metric value above the 0.1 imposed threshold. Next, our
procedure automatically adds another signal `T\_TMODE[0]' as a control
signal because of naming similarity with `T\_TMODE[1]' which was previously
identified as control signal. This is despite the fact that the metric
value of `T\_TMODE[0]' is 0.08, below our 0.1 imposed threshold as shown in
Figure \ref{fig:dsp_cs}. Note that there are no other signals in the group
`T\_TMODE'. These two signals together with signal `T\_IMS' form 8
operation modes, since each of them can take value `0' or `1'.

\begin{figure}[t]
\centering
    \includegraphics[width=4.0in]{figs/dsp_cs.pdf}
    \caption{Control Signals identified for {\tt dsp};
      one signal with metric value less than the Impact Factor is also identified as
      a control signal using group identification}
    \label{fig:dsp_cs}
\end{figure}

\subsection{Comparison with Existing Work \cite{KoDis}}

In our last experiment, we compare our control signals identified for benchmark
{\tt S35932} and benchmark {\tt S38584} using our framework with the
control signals identified using the approach in \cite{KoDis} which is based on 
Automated Test Pattern Generation (ATPG). For benchmark S35932 we identify 
three control signals, `RESET' and `TM0', `TM1' which are the same as
identified in the work \cite{KoDis}. For benchmark {\tt S38584}, we
identify control signal `g35' which is again the same as the one identified
in that work. Figure \ref{fig:S35932_S38584_cs} shows the value of the metric for each of the
identified control signal. Note all metric values are above the 0.1
threshold value.


\begin{figure}[t] \centering
    \includegraphics[width=4.0in]{figs/S35932_S38584_cs.pdf}
    \caption{Control Signals identified for {\tt S35932} and {\tt S38584}}
    \label{fig:S35932_S38584_cs}
\end{figure}

The work \cite{KoDis} only provided results for small benchmarks from the ISCAS'89 
benchmark suite \cite{ISCAS89}. We want to compare our results with the ones obtained
by the ATPG-based method in the work \cite{KoDis} for larger benchmark
suites such as the ISPD'12 and IWLS'05 benchmark suites \cite{ISPD12,IWLS05}. However this can not be done due to the lack
of ATPG tools and the missing detail in \cite{KoDis}.  According to the
work \cite{KoDis}, the signals with care-bit density value larger than a
threshold are considered as control signals. However, this work did not give
any detailed information on how to set the value of this threshold. 
Therefore, we are not comparing our identification results with the work \cite{KoDis} for larger benchmarks.

